// Created by WXX on 2022/6/19 17:09
#include "MyTree.h"
#include <unordered_map>

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了98.68%的用户
 * 内存消耗：24.1 MB, 在所有 C++ 提交中击败了23.64%的用户
 */
class Solution {
public:
    unordered_map<int, int> hash;
    vector<int> ans;
    int maxc = 0;

    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root) {
        if (!root) return 0;
        int sum = root->val + dfs(root->left) + dfs(root->right);
        hash[sum]++;
        if (hash[sum] > maxc) {
            maxc = hash[sum];
            ans = {sum};
        } else if (hash[sum] == maxc) {
            ans.push_back(sum);
        }
        return sum;
    }
};

int main() {

    int nu = INT_MAX;
    vector<int> nums = {
            5,
            2, -5,
    };
    TreeNode *root = MyTree(nums).getRoot();
    OutputBasicArray1D(Solution().findFrequentTreeSum(root));

    return 0;
}
